/**
 * @author: lk
 * @data: 2021/11/10 15:42
 */
package w6_c1_quicksort;

import selectionSort.ArrayGenerator;
import selectionSort.SortingHelper;

/**
 * 自己先写的版本。各种欠妥和错误的写法。
 *
 * @param <E>
 */
public class MyQuickSort<E extends Comparable<E>> {

    public static <E extends Comparable<E>> void sort(E[] arr) {
        sortHelper(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sortHelper(E[] arr, int lo, int hi) {
        if (arr == null || lo >= hi)
            return;
        int pivot = partition3Ways(arr, lo, hi);
//        int pivot = partition_WRONG(arr, lo, hi);
//        int pivot = partition(arr, lo, hi);
        sortHelper(arr, lo, pivot - 1);
        sortHelper(arr, pivot + 1, hi);
    }

    private static <E extends Comparable<E>> int partition(E[] arr, int lo, int hi) {
        int j = lo;
        E e = arr[lo];
        //arr[lo+1,j] < e;arr[j+1,i-1]>=v.
        for (int i = lo + 1; i <= hi; i++) {
            if (arr[i].compareTo(e) < 0) {
                j++;
                swap(arr, i, j);
            }
        }
        swap(arr, lo, j);
        return j;
    }

    /**
     * TODO:
     * 似乎是明白了：为什么需要写i>=j的边界条件。
     * 因为一边的条件是(l,i]&lt;pivot;另一边的条件是(j,h] &gt;pivot，此时若i==j，则因为j是区间内的，
     * 所以j已经是被遍历过的了，其位置是正确的；
     * 而此时的条件，恰是i==j.
     * 若超过也不行，也会错。因为一旦i越界，会错误地交换数据，属于”多此一举“，也会错。
     * 细节太多了。写对真难。
     *
     * @param arr
     * @param lo
     * @param hi
     * @param <E>
     * @return
     */
    private static <E extends Comparable<E>> int partition_WRONG(E[] arr, int lo, int hi) {
        int i = lo + 1, j = hi;
        E e = arr[lo];
        while (i <= j) {
            while (i <= j && arr[i].compareTo(e) < 0)//也错在这了。之前是<而非<=
                i++;
            while (i <= j && arr[j].compareTo(e) > 0)
                j--;
            if (i >= j)
                break;
            //错在这了。到了这一步需要判断i和j的大小，然后再进行交换。否则可能会破坏循环不变量。
            swap(arr, i, j);
            i++;
            j--;
//            if(arr[i] == arr[j] &&arr[i]==e)
        }
        swap(arr, lo, j);
        return j;
    }

    /**
     * 本来是受占新启发写的。但是改来改去还是这个版本，晕。
     * @param arr
     * @param low
     * @param high
     * @param <E>
     * @return
     */
    private static <E extends Comparable<E>> int partition_ZhanXin(E[] arr, int low, int high) {
        //(low+1,i),(j,high]
        int i = low+1, j = high;
        E pivot = arr[low];
        while (true) {//i<j这样的条件似乎没有必要。
            while (i <=j && pivot.compareTo(arr[i]) > 0)
                i++;
            while (i <= j && pivot.compareTo(arr[j]) < 0)
                j--;
            if(i>=j)
                break;
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr,j,low);
        return j;

    }

    /**
     * 错误的二路归并法。后来改对了，但还是不清楚何时用&lt;=何时用&gt;=
     *
     * @param arr
     * @param lo
     * @param hi
     * @param <E>
     */
    private static <E extends Comparable<E>> void sortHelper_WRONG(E[] arr, int lo, int hi) {
        if (arr == null || hi <= lo)
            return;
        E e = arr[lo];
        int index = 0, i;
        for (i = 0; i < arr.length; i++) {//错在这里了。这个循环相当于partition函数，
            // 但是并没有做到将小于pivot的值放到pivot左边，只是将pivot放到了规定的位置。
            if (arr[i].compareTo(e) < 0)
                index++;
        }
        swap(arr, index, lo);
        sortHelper(arr, lo, index - 1);
        sortHelper(arr, index + 1, hi);
    }

    private static <E extends Comparable<E>> void swap(E[] arr, int i, int j) {
        E tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 第一次写的错误版本三路partition。
     *
     * 错误1：根本没有起到三路快排的效果：因为还需要修改返回值，修改递归过程
     * 错误2：循环过程中没有维持循环不变量
     * @param arr
     * @param low
     * @param high
     * @param <E>
     * @return
     */
    private static <E extends Comparable<E>> int partition3Ways(E[] arr, int low, int high) {
        //(low+1,lt]<pivot, (lt,i)==pivot, (gt,high]>pivot;
        int lt = low+1, i = low+1, gt = high;
        E pivot = arr[low];
        for (i = low + 1; i <= gt; ) {
            while(i<=gt && arr[i].compareTo(pivot) < 0)//这句就错了，根本没有维持上面的循环不变量。
                i++;
            if(i>gt)
                break;
            if(arr[i] == pivot) {
                swap(arr, i, ++lt);
                i++;
            }
            else {
                swap(arr, i, gt--);
            }
        }
        swap(arr,lt,low);
        return lt+1;
    }

    public static void main(String[] args) {
        int n = 10;
        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
        SortingHelper.sortTest("MyQuickSort", arr);
        int x = 1;
//        MyQuickSort ,n = 100000000, time = 101.335033 s

    }
}
